//给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字
//符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。 
//
// 示例： 
//
// 
//输入：
//big = "mississippi"
//smalls = ["is","ppi","hi","sis","i","ssippi"]
//输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
// 
//
// 提示： 
//
// 
// 0 <= len(big) <= 1000 
// 0 <= len(smalls[i]) <= 1000 
// smalls的总字符数不会超过 10⁶。 
// 你可以认为smalls中没有重复字符串。 
// 所有出现的字符均为英文小写字母。 
// 
//
// Related Topics 字典树 数组 哈希表 字符串 字符串匹配 滑动窗口 👍 56 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-21 17:37:19
 * @description 面试题 17.17.多次搜索
 */
public class MultiSearchLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MultiSearchLcci fun=new MultiSearchLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int[][] multiSearch1(String big, String[] smalls) {
		List<List<Integer>> list=new ArrayList<>();
		// 对每个小串遍历
		for(int i=0;i<smalls.length;i++){
			List<Integer> loc=new ArrayList<>();
			//注意边界j>0&&j<=big.length()
			// 从左往右，比较 j-smalls[i].length()的子串是否和目标子串相等，
			for(int j=smalls[i].length();j>0&&j<=big.length();j++){
				if(smalls[i].equals(big.substring(j-smalls[i].length(),j))){
					// 相等时加入起点
					loc.add(j-smalls[i].length());
				}
			}
			list.add(new ArrayList<>(loc));
		}
		int[][] ans=new int[smalls.length][];
		for(int k=0;k<smalls.length;k++){
			//构建结果
			ans[k]=new int[list.get(k).size()];
			for(int p=0;p<list.get(k).size();p++) {
				ans[k][p]=list.get(k).get(p);
			}
		}
		return ans;
	}


	class Trie{
		TrieNode root;
		public Trie(String[] words){
			root = new TrieNode();
			for(String word : words){
				TrieNode node = root;
				for(char w : word.toCharArray()){
					int i = w - 'a';
					if(node.next[i] == null){
						node.next[i] = new TrieNode();
					}
					node = node.next[i];
				}
				node.end = word;
			}
		}

		public List<String> search(String str){
			TrieNode node = root;
			List<String> res = new ArrayList<>();
			for(char c : str.toCharArray()){
				int i = c - 'a';
				if(node.next[i] == null){
					break;
				}
				node = node.next[i];
				if(node.end != null){
					res.add(node.end);
				}
			}
			return res;
		}
	}

	class TrieNode{
		String end;
		TrieNode[] next = new TrieNode[26];
	}


	public int[][] multiSearch(String big, String[] smalls) {
		// 先把子串全部加入
		Trie trie = new Trie(smalls);
		//构建一个每个子串的结果集
		Map<String, List<Integer>> hit = new HashMap<>();
		for(int i = 0; i < big.length(); i++){
			// 从每个位置开始搜索，找出所有以这个起点开始的子串
			List<String> matchs = trie.search(big.substring(i));
			for(String word: matchs){
				// 把起点加入结果集
				if(!hit.containsKey(word)){
					hit.put(word, new ArrayList<>());
				}
				hit.get(word).add(i);
			}
		}
		// 构建结果
		int[][] res = new int[smalls.length][];
		for(int i = 0; i < smalls.length; i++){
			List<Integer> list = hit.get(smalls[i]);
			if(list == null){
				res[i] = new int[0];
				continue;
			}
			int size = list.size();
			res[i] = new int[size];
			for(int j = 0; j < size; j++){
				res[i][j] = list.get(j);
			}
		}
		return res;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
